1 citations · 3 across the 15 of their papers we have counts for
15 papers
Families of Linearly -bounded Graphs without Chair or its Induced Sub-graphs
Medha Dhurandhar
A hereditary class H of graphs is -bounded if there is a -binding function f such that for every in , less than or equal to . Here we prove that if a g…
Validity of Borodin and Kostochka Conjecture for classes of graphs without a single, forbidden subgraph on 5 vertices
Medha Dhurandhar
Problem of finding an optimal upper bound for the chromatic no. of a graph is still open and very hard. Borodin and Kostochka Conjecture is still open and if proved will improve Br…
On Validity of Reed Conjecture for Classes of Graphs with Two Forbidden Subgraphs
Medha Dhurandhar
Reed Conjecture is open for more than 20 years now. Here we prove that Reed Conjecture is valid for (1) {P4UnionK1, Kite}-free graphs (2) {Chair, Kite}-free graphs (3) {K2UnionK2co…
Validity of Borodin and Kostochka Conjecture for {4 Times K1}-free Graphs
Medha Dhurandhar
Problem of finding an optimal upper bound for the chromatic no. of even 3K1-free graphs is still open and pretty hard. Here we prove Borodin & Kostochka Conjecture for 4K1-free gra…
On Validity of Reed Conjecture for {P_5, Flag^C}-free graphs
Medha Dhurandhar
Here we prove that Reed Conjecture is valid for {P5, Flag_Complement}-free graphs where FlagComplement is the complement of the Flag graph. Some of the known results follow as coro…
Validity of Borodin & Kostochka Conjecture for a Class of Graphs
Medha Dhurandhar
Borodin & Kostochka conjectured that if maximum degree of a graph is greater than or equal to 9, then the chromatic number of the graph is less than or equal to maximum of ω and ma…
Improvement on Brook theorem for (3 Times K1)-free Graphs
Medha Dhurandhar
Problem of finding an optimal upper bound for the chromatic no. of a (3 Times K1)-free graph is still open and pretty hard. Here we prove that for a (3 Times K1)-free graph G with…
Improvement on Brook theorem for 2K2-free Graphs
Medha Dhurandhar
Here we prove that for a 2K2-free graph G with maximum degree greater than or equal to 5, the chromatic number is less than or equal to max{maximum degree-1, maximum clique size}.…
On the Tight Chromatic Bounds for a Class of Graphs without Three Induced Subgraphs
Medha Dhurandhar
Here we prove that a graph without some three induced subgraphs has chromatic number at the most equal to its maximum clique size plus one. Further we show that the bounds are tigh…
Tight Chromatic Number for a class of Graphs with two forbidden subgraphs
Medha Dhurandhar
Although the chromatic number of a graph is not known in general, attempts have been made to find good bounds for the number. Here we prove that for a graph G with two forbidden su…
Forbidden Subgraph Characterization of Quasi-line Graphs
Medha Dhurandhar
Here in particular, we give a characterization of Quasi-line Graphs in terms of forbidden induced subgraphs. In general, we prove a necessary and sufficient condition for a graph t…
Tight Chromatic Upper Bound for {3 Times K1, {2 Times K1 + (K2 UNION K1)}-free Graphs
Medha Dhurandhar
Problem of finding an optimal upper bound for χ of (3 Times K1)-free graphs is still open and pretty hard. It was proved by Choudum et al that upper bound on the χ of {3 Times K1,…
Tight Chromatic Upper Bound for {3K1, K1+C4}-free Graphs
Medha Dhurandhar
Problem of finding an optimal upper bound for the chromatic no. of 3K1-free graphs is still open and pretty hard. It was proved by Choudum et al that an upper bound on the chromati…
Tight Chromatic Upper Bound for {3K1, C5}-free Graphs
Medha Dhurandhar
Problem of finding an optimal upper bound for a chromatic no. of 3K1-free graphs is still open and pretty hard. Here we find a tight chromatic upper bound for {3K1, C5}-free graphs…
On Chromatic no. of 3K1-free graphs and R(3, k)
Medha S. Dhurandhar
Here we prove that if G has independence no. 2 and clique size omega with omega less than or equal to 11, then (1) chromatic no. is less than or equal to (omega2+12omega-13)/8, if…