Chromatic number and complete graph substructures for degree sequences (Q485549): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
Let \(D\) be a degree sequence and let \(\chi (D)\), \(\omega (D)\), \(h(D)\), and \(H(D)\) denote the maximum chromatic number, the maximum clique number, the size of the largest clique subdivision, and largest clique minor, respectively, over all simple graphs with the degree sequence \(D.\) Clearly, \(\omega (D)\leq h(D)\leq H(D).\) In the paper, a number of inequalities for the given four invariants is derived. Robertson (unpublished) conjectured that \(\chi (D)\leq H(D).\) The main result of the paper states that \(\chi (D)\leq h(D).\) | |||
Property / review text: Let \(D\) be a degree sequence and let \(\chi (D)\), \(\omega (D)\), \(h(D)\), and \(H(D)\) denote the maximum chromatic number, the maximum clique number, the size of the largest clique subdivision, and largest clique minor, respectively, over all simple graphs with the degree sequence \(D.\) Clearly, \(\omega (D)\leq h(D)\leq H(D).\) In the paper, a number of inequalities for the given four invariants is derived. Robertson (unpublished) conjectured that \(\chi (D)\leq H(D).\) The main result of the paper states that \(\chi (D)\leq h(D).\) / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C07 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C83 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C69 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6385400 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
degree sequence | |||
Property / zbMATH Keywords: degree sequence / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
chromatic number of a graph | |||
Property / zbMATH Keywords: chromatic number of a graph / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
clique subdivision | |||
Property / zbMATH Keywords: clique subdivision / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
clique minor | |||
Property / zbMATH Keywords: clique minor / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2166183308 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 0907.1583 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3941433 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hajos' graph-coloring conjecture: Variations and counterexamples / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Rao's degree sequence conjecture / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3577833 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3287781 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3941440 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph minors. XX: Wagner's conjecture / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4242948 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hadwiger number and chromatic number for near regular degree sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some remarks on Hajós' conjecture / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hajós' conjecture for line graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12:52, 9 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Chromatic number and complete graph substructures for degree sequences |
scientific article |
Statements
Chromatic number and complete graph substructures for degree sequences (English)
0 references
9 January 2015
0 references
Let \(D\) be a degree sequence and let \(\chi (D)\), \(\omega (D)\), \(h(D)\), and \(H(D)\) denote the maximum chromatic number, the maximum clique number, the size of the largest clique subdivision, and largest clique minor, respectively, over all simple graphs with the degree sequence \(D.\) Clearly, \(\omega (D)\leq h(D)\leq H(D).\) In the paper, a number of inequalities for the given four invariants is derived. Robertson (unpublished) conjectured that \(\chi (D)\leq H(D).\) The main result of the paper states that \(\chi (D)\leq h(D).\)
0 references
degree sequence
0 references
chromatic number of a graph
0 references
clique subdivision
0 references
clique minor
0 references