{"id":"W4385963754","doi":"10.46298/theoretics.23.9","title":"Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $\\Delta$-Coloring","year":2023,"lang":"en","type":"article","venue":"TheoretiCS","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":1,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo","funders":"European Commission; National Science Foundation","keywords":"Greedy coloring; Graph coloring; Fractional coloring; Edge coloring; Colored; Impossibility; Combinatorics; Complete coloring; Graph; Computer science; Streaming algorithm; Mathematics; Discrete mathematics; Algorithm; Theoretical computer science; Graph power; Line graph; Upper and lower bounds","routes":{"ca_aff":true,"ca_fund":false,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"codex-gemma-dda1882f352a","candidate_categories":["metaepi_narrow"],"consensus_categories":[],"category_scores_codex":[0.0009456562,0.0002901928,0.0003322989,0.0005169454,0.0002329272,0.0002163708,0.001270956,0.0001283637,0.00001077311],"category_scores_gemma":[0.0001218781,0.0002876756,0.0001850435,0.001736297,0.0003001697,0.0002730824,0.0005003409,0.0002586712,0.00003229619],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00008010294,"about_ca_system_score_gemma":0.00005474369,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00002219072,"about_ca_topic_score_gemma":0.00002241671,"domain_scores_codex":[0.9977319,0.0001102361,0.00042085,0.000600532,0.0003459384,0.0007905781],"domain_scores_gemma":[0.998057,0.0008566158,0.0001170799,0.000746325,0.00009846118,0.0001245294],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.000006130307,0.0000738221,0.00006892243,0.00002232397,0.00001761633,0.00002967946,0.001291108,0.0002127861,0.0002317092,0.619348,0.00009591397,0.378602],"study_design_scores_gemma":[0.0004949229,0.0001551518,0.0001844166,0.00009585482,0.000009093868,0.00001137987,0.0003462748,0.4071139,0.003022839,0.5876043,0.0006662956,0.0002955217],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.07282639,0.0001409179,0.9203224,0.0004291994,0.000983774,0.0006089225,0.00007742605,0.0009497771,0.003661231],"genre_scores_gemma":[0.7560757,0.0001066171,0.2427737,0.0002211966,0.0002998704,0.0001638398,0.00005244689,0.00006753422,0.0002390533],"genre_candidate":"methods","genre_consensus":null,"teacher_disagreement_score":0.6832494,"threshold_uncertainty_score":0.9999576,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02922000910492449,"score_gpt":0.260946489951689,"score_spread":0.2317264808467645,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}