Questions on Color-Critical Subgraphs
| Autor: | Nicholas Newman, Matthew Noble |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Mathematics::Commutative Algebra
0211 other engineering and technologies 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Theoretical Computer Science Combinatorics Computer Science::Discrete Mathematics 010201 computation theory & mathematics Discrete Mathematics and Combinatorics Computer Science::Symbolic Computation Mathematics |
| Zdroj: | Graphs and Combinatorics. 37:313-324 |
| ISSN: | 1435-5914 0911-0119 |
| DOI: | 10.1007/s00373-020-02243-z |
| Popis: | In our work, we define a k-tuple of positive integers $$(x_1, \ldots , x_k)$$ to be a $$\chi $$ -sequence if there exists a k-chromatic graph G such that for each $$i \in \{1, \ldots , k\}$$ , the order of a minimum i-chromatic subgraph of G is equal to $$x_i$$ . Denote by $$\mathcal {X}_k$$ the set of all $$\chi $$ -sequences of length k. A very difficult question is to determine, for a given $$(x_1, \ldots , x_k) \in \mathcal {X}_k$$ , the set of all integers y such that $$(x_1, \ldots , x_k, y) \in \mathcal {X}_{k+1}$$ . We propose a few variants of this question and elaborate upon a number of partial results along the way. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink