{"id":"W1984264511","doi":"10.1016/j.tcs.2005.09.028","title":"H-Coloring dichotomy revisited","year":2005,"lang":"en","type":"article","venue":"Theoretical Computer Science","topic":"Advanced Graph Theory Research","field":"Computer Science","cited_by":82,"is_retracted":false,"has_abstract":false,"ca_institutions":"Simon Fraser University","funders":"","keywords":"Constraint satisfaction problem; Mathematics; Greedy coloring; Complete coloring; Combinatorics; Discrete mathematics; Complexity of constraint satisfaction; Computational complexity theory; Automaton; Constraint (computer-aided design); Fractional coloring; List coloring; Constraint satisfaction; Graph coloring; Time complexity; Computer science; Local consistency; Theoretical computer science; Algorithm; Graph","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":["sts"],"consensus_categories":[],"category_scores_codex":[0.00248951,0.0002085399,0.0002247202,0.0003933143,0.0005912127,0.0005601206,0.004723408,0.00004847014,0.00009769015],"category_scores_gemma":[0.0001828865,0.00017441,0.000080562,0.002725777,0.003075098,0.001833872,0.002034958,0.0003571419,0.000498263],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.0001251079,"about_ca_system_score_gemma":0.0001130466,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":5.179318e-7,"about_ca_topic_score_gemma":1.767667e-7,"domain_scores_codex":[0.9964616,0.0001499589,0.0003065983,0.0009754897,0.001109465,0.0009968862],"domain_scores_gemma":[0.9974242,0.0003654603,0.00005986038,0.001405316,0.0002651778,0.0004799343],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.000006219807,0.00003580035,0.00004994603,0.000003392203,0.0000022789,0.0000118831,0.000162138,0.0001954522,0.001251161,0.8896527,0.00003456055,0.1085945],"study_design_scores_gemma":[0.0003089225,0.0001608216,0.0006830332,0.00003433129,0.000002298091,0.0000665386,0.000002831576,0.5950605,0.01496743,0.3853117,0.00306171,0.0003399306],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.02381196,0.00005890368,0.96277,0.001721215,0.0002202082,0.0002258865,6.718613e-7,0.0004498952,0.01074128],"genre_scores_gemma":[0.6958839,0.000006248466,0.3032374,0.0006440771,0.0001847873,0.00001028605,2.338934e-7,0.000007929609,0.00002518019],"genre_candidate":"methods","genre_consensus":null,"teacher_disagreement_score":0.6720719,"threshold_uncertainty_score":0.999638,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01505732805158794,"score_gpt":0.2993394964102967,"score_spread":0.2842821683587087,"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."}}