In graph theory, the (a, b)-decomposition of an undirected graph is a partition of its edges into a + 1 sets, each one of them inducing a forest, except one which induces a graph with maximum degree b. If this graph is also a forest, then we call this a F(a, b)-decomposition.
A graph with arboricity a is (a, 0)-decomposable. Every (a, 0)-decomposition or (a, 1)-decomposition is a F(a, 0)-decomposition or a F(a, 1)-decomposition respectively.
Graph classes
- Every planar graph is F(2, 4)-decomposable.[1]
- Every planar graph <math>G</math> with girth at least <math>g</math> is
- F(2, 0)-decomposable if <math>g \ge 4</math>.[2]
- (1, 4)-decomposable if <math>g \ge 5</math>.[3]
- F(1, 2)-decomposable if <math>g \ge 6</math>.[4]
- F(1, 1)-decomposable if <math>g \ge 8</math>,[5] or if every cycle of <math>G</math> is either a triangle or a cycle with at least 8 edges not belonging to a triangle.[6]
- (1, 5)-decomposable if <math>G</math> has no 4-cycles.[7]
- Every outerplanar graph is F(2, 0)-decomposable[2] and (1, 3)-decomposable.[8]
Notes
Шаблон:Reflist
References (chronological order)
Шаблон:Refbegin
Шаблон:Refend
| Партнерские ресурсы |
|---|
| Криптовалюты |
|
|---|
| Магазины |
|
|---|
| Хостинг |
|
|---|
| Разное |
- Викиум - Онлайн-тренажер для мозга
- Like Центр - Центр поддержки и развития предпринимательства.
- Gamersbay - лучший магазин по бустингу для World of Warcraft.
- Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память.
- Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России.
- Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме.
- Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео.
- Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет
- SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона.
- «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется.
- StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.
- Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено.
- StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.
|
|---|
- ↑ Шаблон:Harvtxt, conjectured by Шаблон:Harvtxt. Improving results by Шаблон:Harvtxt then Шаблон:Harvtxt.
- ↑ 2,0 2,1 Implied by Шаблон:Harvtxt.
- ↑ Шаблон:Harvtxt
- ↑ Implied by Шаблон:Harvtxt, improving results by Шаблон:Harvtxt, then Шаблон:Harvtxt.
- ↑ Independently proved by Шаблон:Harvtxt and implied by Шаблон:Harvtxt, improving results by Шаблон:Harvtxt for girth 11, then Шаблон:Harvtxt for girth 10 and Шаблон:Harvtxt for girth 9.
- ↑ Шаблон:Harvtxt, even if not explicitly stated.
- ↑ Шаблон:Harvtxt, improving results by Шаблон:Harvtxt, then Шаблон:Harvtxt.
- ↑ Proved without explicit reference by Шаблон:Harvtxt.
