Chromatic number and complete graph substructures for degree sequences (Q485549): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
(4 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 | |||
links / mardi / name | links / mardi / name | ||
Revision as of 15:21, 18 April 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