Zobrazeno 1 - 10
of 39
pro vyhledávání: '"Bert Randerath"'
Publikováno v:
Discrete Applied Mathematics. 253:14-24
In this paper, we study the chromatic number of 2 K 2 -free graphs. We show linear χ -binding functions for several subclasses of 2 K 2 -free graphs, namely ( 2 K 2 , H ) -free graphs where H ∈ { h o u s e , g e m , 2 K 1 + K p , ( K 1 ∪ K 2 ) +
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::cf80d5b2e2b0e03b5ef57c2d2b089e24
https://doi.org/10.1016/j.dam.2018.09.030
https://doi.org/10.1016/j.dam.2018.09.030
Autor:
Ingo Schiermeyer, Bert Randerath
Publikováno v:
Graphs and Combinatorics. 35:1-31
A graph G with clique number $$\omega (G)$$ and chromatic number $$\chi (G)$$ is perfect if $$\chi (H)=\omega (H)$$ for every induced subgraph H of G. A family $${\mathcal {G}}$$ of graphs is called $$\chi $$ -bounded with binding function f if $$\ch
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1f34bb2124522fb343acd9d2d2304b64
https://doi.org/10.1007/s00373-018-1999-0
https://doi.org/10.1007/s00373-018-1999-0
WITHDRAWN: Preface: 15th Cologne–Twente Workshop on graphs and combinatorial optimization (CTW 2017)
Publikováno v:
Discrete Applied Mathematics.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::24c91fe74bdb6a551be2ac46736d4c4f
https://doi.org/10.1016/j.dam.2019.10.023
https://doi.org/10.1016/j.dam.2019.10.023
Publikováno v:
Discrete Applied Mathematics. 209:59-67
Caro and Wei independently showed that the independence number (G) of a graph G is at least uV(G)1dG(u)+1. In the present paper we conjecture the stronger bound (G)uV(G)2dG(u)+G(u)+1 where G(u) is the maximum order of a clique of G that contains the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f160fc1dfb75ebf52ee55a967379fdee
https://doi.org/10.1016/j.dam.2015.06.009
https://doi.org/10.1016/j.dam.2015.06.009
Publikováno v:
Filomat. 30:2795-2801
For a graph $G$ a subset $D$ of the vertex set of $G$ is a {\it $k$-dominating set} if every vertex not in $D$ has at least $k$ neighbors in $D$. The {\it $k$-domination number} $\gamma_k(G)$ is the minimum cardinality among the $k$-dominating sets o
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::41d1d9898f53469f7fcd63bfaae65b3c
https://doi.org/10.2298/fil1610795h
https://doi.org/10.2298/fil1610795h
Publikováno v:
Discrete Applied Mathematics. 272:1
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9af889feea71497aacadef7d5b5c0d61
https://doi.org/10.1016/j.dam.2019.12.009
https://doi.org/10.1016/j.dam.2019.12.009
Autor:
Bert Randerath1, Ingo Schiermeyer2
Publikováno v:
Graphs & Combinatorics. Mar2004, Vol. 20 Issue 1, p1-40. 40p.
Autor:
Ingo Schiermeyer, Bert Randerath
Publikováno v:
Discrete Applied Mathematics. 158:1041-1044
The complexity status of the Maximum Independent Set Problem (MIS) for the family of P"5-free graphs is unknown. Although for many subclasses of P"5-free graphs MIS can be solved in polynomial time, only exponential time MIS-algorithms for general gr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::608bd8b27e3b624d4aea33d05e7d0537
https://doi.org/10.1016/j.dam.2010.01.007
https://doi.org/10.1016/j.dam.2010.01.007
Publikováno v:
Theoretical Computer Science. 389:330-335
We show that deciding if a graph without induced paths on nine vertices can be colored with 4 colors is an NP-complete problem, improving a previous NP-completeness result proved by Woeginger and Sgall in 2001. The complexity of 4-coloring graphs wit
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::17762e90800c5f1a01a1462356b2d6a0
https://doi.org/10.1016/j.tcs.2007.09.009
https://doi.org/10.1016/j.tcs.2007.09.009
Publikováno v:
Annals of Mathematics and Artificial Intelligence. 43:173-193
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4167c1e98e7380b90487741c6dd4a744
https://doi.org/10.1007/s10472-005-0428-2
https://doi.org/10.1007/s10472-005-0428-2